package study.datastructure.link;/**
 * @program: datastructure
 * @author: lcy
 * @create: 2025-02-01 11:00
 */

import study.datastructure.link.leetcode.ListNode;

import java.io.IOException;
import java.nio.file.Files;
import java.nio.file.Paths;
import java.util.*;
import java.util.concurrent.Executors;
import java.util.concurrent.ThreadPoolExecutor;

/**
 * 2025/2/1,
 */


public class s1 {


    /**
     * 相交链表
     * 给定两个（单向）链表，判定它们是否相交并返回交点。请注意相交的定义基于节点的引用，而不是基于节点的值。
     *
     * @param headA
     * @param headB
     * @return a1 a2
     * c1 c2 c3
     * b1
     * <p>
     * A: 1 -> 2 -> 3
     * \
     * -> 6 -> 7
     * /
     * B:     4 -> 5
     * <p>
     * a + c + b = = b + c + a
     */
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {

        if (headA == null || headB == null) return null;


        ListNode pA = headA;
        ListNode pB = headB;

        while (pA != pB) {
            pA = (pA == null) ? headB : pA.next;
            pB = (pB == null) ? headA : pB.next;
        }

        return pA;

    }

    /**
     * 给你一个链表的头节点 head ，判断链表中是否有环。
     *
     * @param head
     * @return
     */
    public boolean hasCycle(ListNode head) {
        if (head == null || head.next == null) return false;
        ListNode p = head;
        HashSet<ListNode> set = new HashSet<>();
        while (p != null) {
            if (set.contains(p)) return true;
            set.add(p);

            p = p.next;

        }

        return false;


    }

    /**
     * 快慢指针法
     * 给你一个链表的头节点 head ，判断链表中是否有环。
     *
     * @param head
     * @return
     */
    public boolean hasCycle1(ListNode head) {
        if (head == null || head.next == null) return false;

        ListNode slow = head;
        ListNode fast = head.next;

        while (slow != fast) {
            if (fast == null || fast.next == null) return false;

            slow = slow.next;
            fast = fast.next.next;
        }
        return true;


    }

    /**
     * 快慢指针法 (简化)
     * 给你一个链表的头节点 head ，判断链表中是否有环。
     *
     * @param head
     * @return
     */
    public boolean hasCycle2(ListNode head) {
        ListNode slow = head, fast = head;

        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) return true;

        }
        return false;


    }

    /**
     * 移动零
     * 给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
     * 0 1 0 3 12
     * 1 3 12 0 0
     * j : 非零交换的下一个位置
     * 0
     * i
     *
     * @param nums
     */
    public void moveZeroes(int[] nums) {
        int j = 0;

        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != 0) {

                if (i != j) {
                    int temp = nums[i];
                    nums[i] = nums[j];
                    nums[j] = temp;
                }
                j++;
            }

        }
    }


    /**
     * 环形链表 II
     * <p>
     * 给定一个链表的头节点  head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
     *
     * @param head
     * @return
     */
    public ListNode detectCycle(ListNode head) {
        if (head == null) {
            return null;
        }
        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;

            if (slow == fast) {
                ListNode p = head;
                while (p != slow) {
                    p = p.next;
                    slow = slow.next;
                }
                return p;
            }


        }
        return null;
    }

    /**
     * 最大子数组和
     * <p>
     * 给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
     * <p>
     * 子数组
     * 是数组中的一个连续部分。
     * <p>
     * currentSum = 5
     * maxGlobalSum = 5
     * 9
     * <p>
     * maxC
     * <p>
     * 5  9
     * 9  8
     * 9   16
     * 16  8
     * <p>
     * <p>
     * 5 4  -1 7 8
     *
     * @param nums
     * @return
     */
    public int maxSubArray(int[] nums) {
        if (nums == null || nums.length == 0) return 0;

        int currentSum = nums[0];
        int maxSum = nums[0];

        for (int i = 1; i < nums.length; i++) {
            currentSum = Math.max(currentSum + nums[i], nums[i]);
            maxSum = Math.max(maxSum, currentSum);
        }

        return maxSum;
    }


    /**
     * 搜索二维矩阵 II
     * <p>
     * 每行中的整数从左到右按非严格递增顺序排列。
     * 每行的第一个整数大于前一行的最后一个整数。
     * 给你一个整数 target ，如果 target 在矩阵中，返回 true ；否则，返回 false 。
     *
     * @param matrix
     * @param target
     * @return
     */
    public boolean searchMatrix(int[][] matrix, int target) {

        if (matrix == null || matrix.length == 0) return false;
        int i = matrix.length;
        int j = matrix[0].length;

        for (int k = 0; k < i; k++) {
            for (int l = 0; l < j; l++) {
                if (matrix[k][l] == target) {
                    return true;
                }
            }
        }

        return false;

    }


    public boolean searchMatrix1(int[][] matrix, int target) {

        if (matrix == null || matrix.length == 0) return false;
        int m = matrix.length, n = matrix[0].length;

        //二分查找
        int low = 0, high = m * n - 1;

        while (low <= high) {
            int mid = (low + high) / 2;
            int midValue = matrix[mid / n][mid % n];
            if (midValue > target) {
                high = mid - 1;
            } else if (midValue < target) {
                low = mid + 1;
            } else {
                return true;
            }
        }
        return false;
    }


    /**
     * 合并数组
     * [ [1,3] [2,6] [8,10] [15,18]]
     * <p>
     * <p>
     * <p>
     * <p>
     * 以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi]
     * 请你合并所有重叠的区间，并返回 一个不重叠的区间数组，
     * 该数组需恰好覆盖输入中的所有区间 。
     *
     * @param intervals
     * @return
     */
    public int[][] merge(int[][] intervals) {

        int[][] array = new int[][]{{1, 3}, {2, 6}, {8, 10}, {15, 18}};


        return null;

    }

    /**
     * 两数相加
     * 给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
     * <p>
     * 请你将两个数相加，并以相同形式返回一个表示和的链表。
     * <p>
     * 你可以假设除了数字 0 之外，这两个数都不会以 0 开头。
     * <p>
     * 2  4  3
     * <p>
     * 5  6  4
     * <p>
     * 0
     * 1
     * 7  0   8
     *
     * @param l1
     * @param l2
     * @return
     */
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {

        ListNode dummy = new ListNode(0);
        ListNode curr = dummy;

        // 进位
        int carry = 0;

        while (l1 != null || l2 != null || carry != 0) {

            int v1 = (l1 == null) ? 0 : l1.val;
            int v2 = (l2 == null) ? 0 : l2.val;
            int sum = v1 + v2 + carry;

            carry = sum / 10;
            curr.next = new ListNode(sum % 10);
            curr = curr.next;
            if (l1 != null) {
                l1 = l1.next;
            }
            if (l2 != null) {
                l2 = l2.next;
            }
        }


        return dummy.next;
    }


    /**
     * 归并排序链表
     * 给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。
     *
     * @param head
     * @return
     */
    public ListNode sortList(ListNode head) {
        // 基线条件 小于等于1 返回
        if (head == null || head.next == null) {
            return head;
        }

        // 分治
        ListNode fast = head.next, slow = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        ListNode tmp = slow.next;
        slow.next = null;
        ListNode left = sortList(head);
        ListNode right = sortList(tmp);

        // 归并
        ListNode h = new ListNode(0);
        ListNode res = h;
        while (left != null && right != null) {
            if (left.val < right.val) {
                h.next = left;
                left = left.next;
            } else {
                h.next = right;
                right = right.next;
            }
            h = h.next;
        }
        h.next = left != null ? left : right;
        return res.next;
    }


    /**
     * 归并排序单向链表
     * 复杂度 nlogn logn
     *
     * @param head
     * @return
     */
    public ListNode sortList1(ListNode head) {
        if (head == null || head.next == null) return head;

        ListNode slow = head;
        ListNode fast = head.next;

        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        ListNode tmp = slow.next;
        slow.next = null;


        ListNode left = sortList1(head);
        ListNode right = sortList1(tmp);


        ListNode h = new ListNode(0);
        ListNode curr = h;
        while (left != null && right != null) {
            if (left.val < right.val) {
                curr.next = left;
                left = left.next;
            } else {
                curr.next = right;
                right = right.next;
            }
            curr = curr.next;
        }
        curr.next = (left != null) ? left : right;
        return h.next;
    }

    public int[] sortArray(int[] nums) {
        int a = 10;
        StringBuilder s = new StringBuilder("aaa");
        System.out.println("s = " + s);
        //s1.inc(a, s);
        System.out.println("a = " + s);
        return nums;
    }

    public static void inc(int a, StringBuilder b) throws IOException {
        b.append("bbb");
        Files.copy(Paths.get("aaa"), Paths.get("bbb"));
    }


    /**
     * 数组中第k个最大的元素
     * <p>
     * 给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
     * <p>
     * 请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
     * <p>
     * 你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。
     *
     * @param nums
     * @param k
     * @return
     */
    public int findKthLargest(int[] nums, int k) {
        if (nums == null || nums.length == 0) return 0;

        PriorityQueue<Integer> queue = new PriorityQueue<>();
        for (int num : nums) {
            queue.offer(num);
            if (queue.size() > k) {
                queue.poll();
            }
        }
        return queue.peek();

        // 最小堆 堆顶 是最大元素中第k个最小值 即第k大


    }

    /**
     * 数组中的前K个频率最多的元素
     *
     * @param nums
     * @param k
     * @return
     */

    public int[] topKFrequent(int[] nums, int k) {
        if (nums == null || nums.length == 0) return new int[0];

        Map<Integer, Integer> map = new HashMap<>();

        for (int num : nums) {
            map.put(num,map.getOrDefault(num,0)+1);
        }

        // 遍历map，用最小堆保存频率最大的 前k个元素
        PriorityQueue<Integer> pq = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer a, Integer b) {
                return map.get(a) - map.get(b);
            }
        });
        for (Integer key : map.keySet()) {
            if (pq.size() < k) {
                pq.offer(key);
            } else if (map.get(key) > map.get(pq.peek())) {
                pq.remove();
                pq.add(key);
            }
        }

       int [] res = new int[k];
        while (!pq.isEmpty()) {
            res[--k] = pq.poll();
        }

        return res;
    }




    public static void main(String[] args) {
        s1 s1 = new s1();
        int[] nums = {1, 2, 3, 4, 5};
        s1.sortArray(nums);
    }

}

